1. Field of the Invention
The present invention relates to a method for matching one signature with another and more specifically to a method for verifying signatures written as a part of a transaction.
2. Description of Prior Art
Existing debit or credit cards have on them a signature provided by a person to whom the credit card has been issued. During a debit or credit card transaction the person making the transaction signs a voucher and the other party to the transaction compares the two signatures before completing the transaction. A similar operation is carried out for check verification. As the card used for the transaction carries the signature of the holder of the card, it is possible for someone who obtains the card illegally to practice the signature and so obtain money or goods by false pretences. The problem is a major one and it is estimated that some eight hundred million dollars are lost in this way annually.
A signature represents a two-dimensional pattern, but by the nature of its creation from human writing, it can be classified according to a one-dimensional variable-time method. Variations in this method have been proposed. For example, Herbet and Lui published a method based on the use of acceleration-time functions that reduced the level of acceptance of forgeries by some 98%.
Other prior art methods have been used for detecting authentic and forged signatures. For example, the method of U.S. Pat. No. 5,202,930 (Livshitz et al.) is concerned with the distribution of stylus accelerations during the writing of test and reference signatures. Livshitz et al. sets out to remove distorting effects, which can arise due to causes such as a test signature being written at a different overall speed from the reference signature. This method differs from the current invention, which is concerned with the relative positions of a stylus at given intervals after the start of the writing of reference and test signatures.
Livshitz et al. is an example of a well-known xe2x80x9csliding window xe2x80x9d technique for recognizing non-linear distortions in time between two time-dependent functions. The method finds localized links between regions of a test function or window and a reference function or window, sliding one window against the other and observing the position in the test window where local correlations are maximized. The technique compares the distance that the function or window had to slide in several corresponding intervals with an authenticated signature. The distances of the several windows are then entered into a classification algorithm such as a histogram.
The drawback with the Livshitz approach is that the position in the test function giving the best correlation may not correspond to the optimal linkage between the functions. The problem can be exemplified by an attempt to match the signature xe2x80x9cFollyxe2x80x9d. The two xe2x80x9clxe2x80x9ds in the signature would provide identical sliding window fits at two different times, as the first xe2x80x9clxe2x80x9d in one signature would match equally well with either xe2x80x9clxe2x80x9d in the second signature. This difficulty is overcome in the present invention by minimizing a total energy term with correlation, spatial distortion, bond and timing distortion terms which ensures that the whole signature has a smooth low-curvature spatial distortion that simultaneously gives a good correlation along the complete signature. Any sharp error such as a match to the wrong xe2x80x9clxe2x80x9d in xe2x80x9cFollyxe2x80x9d gives an immediate increase in the spatial distortion energy. It is to be noted that while in Livshitz et al. only correlation is optimized, and only time distortions are measured, the present invention introduces the distinct concept of spatial distortion curvature. It is only in the current invention that the two concepts of correlation and spatial distortion appear as separate and distinct terms and only the summed total is minimized.
U.S. Pat. No. 5,101,437 (Plamondon) is concerned with the creating of parameters corresponding to handwritten strings, based on the presence or lifting of a pen during the signature. As in the current invention, Plamondon teaches correlation of the average vectors as an initial step. However, the Plamondon technique proceeds by deriving evaluating functions, concerned with the curvilinear and angular velocities of the signatures, which are compared in order individually, so that the signature is deemed a forgery if any of the functions do not meet the specified criteria.
The current invention overcomes the shortcomings with the prior art by providing a matching technique, which first uses the mean vector to find distortion values for a set of points along two signatures, and then matches those points which have a minimum distortion and maximum correlation
In accordance with a preferred embodiment of the present invention, there is provided a method for matching a reference signature designated (R) with a questioned, signature designated (Q) to determine whether the signatures are written by a specified person, comprising the operations of creating a mapping between points in the two signatures to be compared, measured at corresponding times after the commencement of the writing of each of the signatures, which maximizes the correlation between the spatial neighborhoods of the measured points in the signatures and simultaneously minimizes the curvature of the distortions in the mapping. Quantitative measures of both the maximum of the correlations between the spatial neighborhoods of the measured points in the signatures and the minimum of the curvature of the distortions are provided, thereby to giving a measure of the similarity between the two signatures, comparing the measure of similarity between the signatures with an accepted criterion of similarity indicative of an acceptable probability that both signatures were written by the specified person and providing an indication of the acceptance or rejection thereof.
A novel aspect of the current invention is the simultaneous use of correlation of the average vectors, as in Plamondon, and a time mapping similar in intent to that of Livshitz et al. to minimize a total energy function which finds a smooth, low curvature, distortion between the signatures and simultaneously maximizes the correlation between the matched points of the signature. The present invention also makes use of time variations to compare signatures and has some similarities to the method of spectrum matching published in UK Patent Application 2,225,149A. The essential difference, however, is that a signature represents a continuous pair of x and y spatial variables recorded as a function of time, rather than sets of variables defined at the discrete times corresponding to peaks in the spectra to be matched. The nature of the correlation, therefore, is quite different.
The present invention goes beyond the prior art and does not involve sliding a function representing a trial signature against another function representing a reference signature to determine the best fit between them as suggested in Livshitz et al., but uses a procedure in which trial linkages at a chosen time after the start of the writing of the two signatures are made, and then refined using a Monte Carlo simulated annealing procedure so as to maximize local correlations between the test and reference signatures, while minimizing the elastic distortion energies of the linkages between corresponding points on the two signatures (this is what is meant by minimizing the curvature of the distortions in the mapping). This concept is not relevant to the technique adopted in Livshitz et al. because Livshitz et al. is concerned solely with time distortions, while the present invention is concerned with spatial differences with time components being an independent variable under the control of the user.
In summary, there are two important differences between the approach of Livshitz et al. and the current invention. Whereas Livshitz et al. use a xe2x80x9csliding windowxe2x80x9d approach to find a time shift which minimizes time distortion, the current invention minimizes the curvature of the time distortion. This difference is crucial. The current invention defines a distortion energy Edist, which correctly describes the elastic energy of a rubber sheet, stretched from one signature to another. There is no counterpart to this energy in Livshitz et al.
The second crucial difference with Livshitz et al is that they make their classification from the histogram of phase distortions, which uses only the timing information. The current invention uses a more complex function including correlation, distortion, bond and timing terms.
Applying the Plamondon equations to Livshitz et al. would not disclose the current invention""s matching technique, which first uses the mean vector to find distortion values for a set of points along two signatures, and then matches those points which have a minimum distortion and maximum correlation.